package leetcode每日一题.leetcode20212;

/**
 * 1. 问题描述
 *      在MATLAB中，有一个非常有用的函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。
 *      给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。
 *      重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。
 *      如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。
 *
 * 2. 算法分析
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q018_重塑矩阵 {

    /**
     * 将二维矩阵拉直，扫描拉直后的数组，然后注意换行即可
     * 时间复杂度为O(n^2) 空间复杂度为O(n)
     * @param nums
     * @param r
     * @param c
     * @return
     */
    public int[][] matrixReshape1(int[][] nums, int r, int c) {
        int row = nums.length; // 实际矩阵的行数
        int col = nums[0].length; // 实际矩阵的列数
        if(row * col != r * c) { // 此时无法reshape
            return nums;
        }
        // 如果可以，我们需要将row行col列的矩阵转化为r行c列的矩阵
        int[] temp = new int[r*c]; // 将nums矩阵拉直
        int index = 0;
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                temp[index] = nums[i][j];
                index++;
            }
        }
        int[][] res = new int[r][c];
        res[0][0] = temp[0];
        int j = 0; // 行索引
        for(int i = 1; i < temp.length; i++) { // 扫描拉直后的矩阵
            // 每隔c个元素换行
            if(i % c == 0) { // 此时需要换行
                j++;
            }
            res[j][i % c] = temp[i];
        }
        return res;
    }


    /**
     * 优化，看是否不需要额外的空间，直接从二维数组上找索引规律?
     * 本题的主要考点在于：二维数组的扁平化操作，将二维映射到一维(i,j) ---> i * n + j(当然扁平化操作不只有一种)
     * 假设当前第x元素为新数组中的从行到列开始数的位置，则该原在元素数组中的坐标位置，不防设元素数组中的索引为(i,j)
     * i * n + j = x,则i = x / n - j / n 由j / n 在计算机元素中为0(j < n)  j = x % n
     * @param nums
     * @param r
     * @param c
     * @return
     */
    public int[][] matrixReshape2(int[][] nums, int r, int c) {
        int row = nums.length; // 实际矩阵的行数
        int col = nums[0].length; // 实际矩阵的列数
        if(row * col != r * c) { // 此时无法reshape
            return nums;
        }
        int[][] res = new int[r][c];
        // 此时考虑一个二维到一维的映射,逻辑上的映射，不需要额外使用空间来存储拉直后的数组
        for(int i = 0; i < row * col; i++) {
            res[i / c][i % c] = nums[i / col][i % col];
        }
        return res;
    }
}
